#pragma once
#include <algorithm>
#include <memory>
#include <random>
#include <functional>
#include<iterator>

namespace redis {
    template<typename T, typename Compare = std::less<T>>
    class skip_list {
    public:
        typedef T data_type;
    private:
        static constexpr std::size_t init_level = 32;

        struct skip_node {
            struct skip_level {
                std::size_t step;
                skip_node* next;
                skip_node* pre;

                skip_level() : step(0), next(nullptr), pre(nullptr) {}
            } *node_levels = nullptr;

            std::size_t level;
            std::unique_ptr<data_type> data;

            skip_node() = delete;

            explicit skip_node(std::size_t _level) : level(_level), node_levels(new skip_level[_level]) {}

            ~skip_node() {
                delete node_levels;
            }
        };

        std::unique_ptr<skip_node> head;
        std::function<bool(const data_type&, const data_type&)> compare_fun = Compare();
        std::size_t len;
        std::size_t max_level;

        static std::random_device rd;
        static std::mt19937 gen;
        static std::uniform_int_distribution<> dis;

        struct iterator {
        private:
            skip_node* node;
        public:
            friend class skip_list;
            typedef const data_type value_type;
            typedef std::size_t difference_type;
            typedef const data_type* pointer;
            typedef const data_type& refernece;
            typedef std::bidirectional_iterator_tag iterator_tag;

            iterator() = default;

            explicit iterator(skip_node* _node) : node(_node) {}

            iterator(const iterator& iter) = default;

            iterator& operator=(const iterator& iter) = default;

            bool operator==(const iterator& iter) const {
                return node == iter.node;
            }

            bool operator!=(const iterator& iter) const {
                return node != iter.node;
            }

            refernece operator*() {
                return *(node->data);
            }

            pointer operator->() {
                return node->data.get();
            }

            iterator& operator++() {
                node = node->node_levels[0].next;
                return *this;
            }

            iterator operator++(int) {
                skip_node* next = node;
                node = node->node_levels[0].next;
                return iterator(next);
            }

            iterator& operator--() {
                node = node->node_levels[0].pre;
                return *this;
            }

            iterator operator--(int) {
                skip_node* next = node;
                node = node->node_levels[0].pre;
                return iterator(next);
            }
        };

        typedef iterator const_iterator;
        typedef std::reverse_iterator<iterator> reverse_iterator;
        typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

        std::size_t random_level();

        skip_node* insert_data(const data_type& data);

        skip_node* erase_range(skip_node* be, skip_node en);

        skip_node* erase_node(skip_node* node);

        size_t erase_data(const data_type& data);

        skip_node* find_upper(const data_type& data) const;

        skip_node* find_lower(const data_type& data) const;

    public:
        skip_list();

        skip_list(const skip_list& skl);

        skip_list(skip_list&& skl) noexcept;

        skip_list& operator=(const skip_list& skl);

        skip_list& operator=(skip_list&& skl) noexcept;

        iterator insert(data_type&& data) noexcept;

        iterator insert(const data_type& data);

        const_iterator find(const data_type& data) const;

        const_iterator upper_bound(const data_type& data) const;

        const_iterator lower_bound(const data_type& data) const;

        iterator erase(iterator iter);

        iterator erase(iterator it1, iterator it2);

        size_t erase(const data_type& data);

        iterator begin() const;

        iterator end() const;

        void clear();

        ~skip_list();

        typedef iterator iterator;
    };

    template<typename T,typename Comapare>
    std::random_device skip_list<T, Comapare>::rd;


    template<typename T, typename Comapare>
    std::mt19937 skip_list<T, Comapare>::gen(skip_list<T,Comapare>::rd());

    template<typename T, typename Comapare>
    std::uniform_int_distribution<> skip_list<T, Comapare>::dis(1,skip_list<T,Comapare>::init_level);

    template<typename T, typename Compare>
    skip_list<T, Compare>::skip_list() :head(std::make_unique<skip_node>(init_level)), len(0), max_level(0) {
        for (int i = 0; i < head->level; i++) {
            head->node_levels[i].next = head.get();
            head->node_levels[i].pre = head.get();
        }
    }

    template<typename T, typename Compare>
    inline std::size_t skip_list<T, Compare>::random_level()
    {
        return skip_list<T, Compare>::dis(skip_list<T, Compare>::gen);
    }

    template<typename T, typename Compare>
    typename skip_list<T, Compare>::skip_node* skip_list<T, Compare>::insert_data(const data_type& data) {
        skip_node* nnode = head.get();
        int level_index = max_level - 1;
        auto* node = new skip_node(random_level());
        node->data = std::make_unique<data_type>((data));
        for (int i = 0; i < node->level; i++) {
            node->node_levels[i].pre = nnode;
            node->node_levels[i].next = nnode;
        }
        while (level_index >= 0) {
            while (nnode->node_levels[level_index].next != head.get() &&
                !compare_fun(data,*( nnode->node_levels[level_index].next->data))) {
                nnode = nnode->node_levels[level_index].next;
            }
            if (node->level > level_index) {
                node->node_levels[level_index].pre = nnode;
                node->node_levels[level_index].next = nnode->node_levels[level_index].next;
            }
            level_index--;
        }
        if (nnode != head.get()) {
            if (!compare_fun(*(nnode->data), data)) {
                delete node;
                return nnode;
            }
        }
        len++;
        max_level = std::max(max_level, node->level);
        for (int i = 0; i < node->level; i++) {
            node->node_levels[i].pre->node_levels[i].next = node;
            node->node_levels[i].next->node_levels[i].pre = node;
        }
        return node;
    }

    template<typename T, typename Compare>
    typename skip_list<T, Compare>::skip_node* skip_list<T, Compare>::find_lower(const data_type& data) const {
        skip_node* nnode = head.get();
        int level_index = max_level - 1;
        while (level_index >= 0) {
            while (nnode->node_levels[level_index].next != head.get() &&
                compare_fun(*nnode->node_levels[level_index].next->data, data)) {
                nnode = nnode->node_levels[level_index].next;
            }
            level_index--;
        }
        return nnode->node_levels[0].next;
    }

    template<typename T, typename Compare>
    typename skip_list<T, Compare>::skip_node* skip_list<T, Compare>::find_upper(const data_type& data) const {
        skip_node* nnode = head.get();
        int level_index = max_level - 1;
        while (level_index >= 0 ) {
            while (nnode->node_levels[level_index].next != head.get() &&
                !compare_fun(data,* nnode->node_levels[level_index].next->data)) {
                nnode = nnode->node_levels[level_index].next;
            }
            level_index--;
        }
        return nnode->node_levels[0].next;
    }

    template<typename T, typename Compare>
    typename skip_list<T, Compare>::skip_node*
        skip_list<T, Compare>::erase_range(skip_list::skip_node* be, skip_list::skip_node en) {
        skip_node* node = be;
        while (node != en) {
            node = erase_node(node);
        }
        return node;
    }

    template<typename T, typename Compare>
    size_t skip_list<T, Compare>::erase_data(const data_type& data) {
        skip_node* node = find_lower(data);
        if (node!=head.get()&&(!compare_fun(*node->data, data)) && (!compare_fun(data, *node->data))) {
            erase_node(node);
            return 1;
        }
        else {
            return 0;
        }
    }

    template<typename T, typename Compare>
    typename skip_list<T, Compare>::skip_node* skip_list<T, Compare>::erase_node(skip_list::skip_node* node) {
        skip_node* next = node->node_levels[0].next;
        for (int i = 0; i < node->level; i++) {
            node->node_levels[i].next->node_levels[i].pre = node->node_levels[i].pre;
            node->node_levels[i].pre->node_levels[i].next = node->node_levels[i].next;
        }
        size_t level = node->level;
        while (level > 0 && node->node_levels[level].next == head.get()) {
            level--;
        }
        len--;
        max_level = level;
        delete node;
        return next;
    }

    template<typename T, typename Compare>
    skip_list<T, Compare>::~skip_list() {
        skip_node* node = head->node_levels[0].next;
        while (node != head.get()) {
            skip_node* next = node;
            node = node->node_levels[0].next;
            delete next;
        }
    }

    template<typename T, typename Compare>
    skip_list<T, Compare>::skip_list(const skip_list& skl) :head(std::make_unique<skip_node>(init_level)), len(0), max_level(0) {
        for (iterator it = skl.begin(); it != skl.end(); it++) {
            insert(*it);
        }
    }

    template<typename T, typename Compare>
    skip_list<T, Compare>::skip_list(skip_list&& skl) noexcept :head(std::move(skl.head)), len(skl.len), max_level(skl.max_level) {
    }

    template<typename T, typename Compare>
    skip_list<T, Compare>& skip_list<T, Compare>::operator=(const skip_list& skl) {
        if (&skl == this) {
            return *this;
        }
        clear();
        for (auto& it : skl) {
            insert(it);
        }
        return *this;
    }

    template<typename T, typename Compare>
    void skip_list<T, Compare>::clear() {
        for (iterator it = begin(); it != end(); it = erase(it));
    }

    template<typename T, typename Compare>
    skip_list<T, Compare>& skip_list<T, Compare>::operator=(skip_list&& skl) noexcept {
        if (&skl == this) {
            return *this;
        }
        clear();
        head = std::move(skl.head);
        len = skl.len;
        max_level = skl.max_level;
        return *this;
    }

    template<typename T, typename Compare>
    inline typename skip_list<T, Compare>::iterator skip_list<T, Compare>::insert(data_type&& data) noexcept {
        return iterator(insert_data(std::forward<data_type>(data)));
    }

    template<typename T, typename Compare>
    inline typename skip_list<T, Compare>::iterator skip_list<T, Compare>::insert(const data_type& data)
    {
        return iterator(insert_data((data)));
    }

    template<typename T, typename Compare>
    typename skip_list<T, Compare>::iterator skip_list<T, Compare>::find(const data_type& data)const {
        iterator iter = iterator(find_upper(data));
        if (!compare_fun(*iter, data)) {
            return iter;
        }
        return iterator(head.get());
    }

    template<typename T, typename Compare>
    typename skip_list<T, Compare>::const_iterator skip_list<T, Compare>::upper_bound(const data_type& data) const {
        return iterator(find_upper(data));
    }

    template<typename T, typename Compare>
    typename skip_list<T, Compare>::const_iterator skip_list<T, Compare>::lower_bound(const data_type& data) const {
        return iterator(find_lower(data));
    }

    template<typename T, typename Compare>
    typename skip_list<T, Compare>::iterator skip_list<T, Compare>::erase(skip_list::iterator iter) {
        return iterator(erase_node(iter.node));
    }

    template<typename T, typename Compare>
    typename skip_list<T, Compare>::iterator skip_list<T, Compare>::erase(skip_list::iterator it1, skip_list::iterator it2) {
        return skip_list::iterator(erase_range(it1.node, it2.node));
    }

    template<typename T, typename Compare>
    size_t skip_list<T, Compare>::erase(const data_type& data) {
        return erase_data(data);
    }

    template<typename T, typename Compare>
    typename skip_list<T, Compare>::iterator skip_list<T, Compare>::begin() const {
        return iterator(head->node_levels[0].next);
    }

    template<typename T, typename Compare>
    typename skip_list<T, Compare>::iterator skip_list<T, Compare>::end() const {
        return iterator(head.get());
    }

}

